//package Test;
//
//import javax.swing.tree.TreeNode;
//import java.util.ArrayList;
//import java.util.List;
//public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//    TreeNode(int val) { this.val = val; }
//    TreeNode(int val, TreeNode left, TreeNode right) {
//          this.val = val;
//          this.left = left;
//          this.right = right;}
//}
//
//class Solution {
//    public List<Integer> preorderTraversal(TreeNode root) {
//        if(root == null) return null;
//        List<Integer> ret = new ArrayList<>();
//        ret.add(root.val);
//        List<Integer> rightTree = preorderTraversal(root.right);
//        List<Integer> leftTree = preorderTraversal(root.left);
//        ret.addAll(rightTree);
//        ret.addAll(leftTree);
//        return ret;
//    }
//}